package com.leetcode.根据数据结构分类.并查集;

import java.util.HashMap;
import java.util.List;

/**
 * @author: ZhouBert
 * @date: 2021/1/6
 * @description: 399. 除法求值
 * https://leetcode-cn.com/problems/evaluate-division/
 * 通过题目深入想了一下并查集，发现是个二维的，即具有传递性。
 * 一旦有两个点属于同一个集合，那么与之相关的其他点都在这个集合里（两点确定一条直线）
 * https://leetcode-cn.com/problems/evaluate-division/solution/399-chu-fa-qiu-zhi-nan-du-zhong-deng-286-w45d/
 * 终于承认这个题目好难，暂时木有办法解决。
 * liweiwei 说的栈 -> 递归的思路，有点启发，下次注意看看栈的结构能不能直接转为递归！
 */
public class B_399_除法求值 {


    /**
     * 刚开始接触时发现题目很难理解，因为由抽象的数组介绍带入到场景里有些不适应；
     * 理解了以后发现很难从场景和数据中代入已有的知识来解决问题！——就是想不到用并查集
     * 看了分析以后：
     * 1.根据 equations + values 规划并查集；
     * 2.从 queries 中查找并查集关系，如果找到-> 计算；没有找到-> -1
     *
     * @param equations
     * @param values
     * @param queries
     * @return
     */
    public double[] calcEquation(List<List<String>> equations, double[] values, List<List<String>> queries) {
        //int[] parents = new int[27];
        //使用一个map 来存储数值关系//还是决定用另一个数组存储数值关系
        //HashMap<Character, String> map = new HashMap<>();
        //int[] vs = new int[27];
        //发现元素不是单字母，而是 String ，于是用 HashMap
        HashMap<String, String> parentsMap = new HashMap<>();
        HashMap<String, Double> valuesMap = new HashMap<>();


        //根据前提已知，equations 匹配 values
        for (int i = 0; i < equations.size(); i++) {
            //合并
            union(parentsMap, valuesMap, equations.get(i), values[i]);
        }

        //
        double[] res = new double[queries.size()];
        double defaultValue = -1.0f;
        for (int i = 0; i < queries.size(); i++) {
            String first = queries.get(i).get(0);
            String second = queries.get(i).get(1);
            if (!isSame(parentsMap, first, second)) {
                //如果不是同个集合
                res[i] = defaultValue;
            } else {
                res[i] = valuesMap.get(first) / valuesMap.get(second);
            }

        }
        return res;
    }


    private void union(HashMap<String, String> parentsMap, HashMap<String, Double> valuesMap, List<String> list, double value) {



    }

    private boolean isSame(HashMap<String, String> parentsMap, String first, String second) {
		return false;
	}


    public static void main(String[] args) {

    }
}
